1. Field of the Invention
The present invention relates to a content addressable memory and, more particularly, to a content addressable memory with reduced instantaneous current and power consumption during a search.
2. Description of the Related Art
A content addressable memory (CAM) is a memory cell array which has been modified to facilitate a high-speed search of the contents of the array. Any conventional memory cell structure, such as a static random access memory (SRAM), a dynamic random access memory (DRAM), or a non-volatile memory (NVM), can be modified to form a CAM.
FIG. 1 shows a circuit diagram that illustrates a prior-art, SRAM cell 100. As shown in FIG. 1, SRAM cell 100, which is a six-transistor structure, includes a first transistor M1 that has a gate connected to a word line WORD, a drain connected to a bit line BIT, and a source connected to a first intermediate node N1. Cell 100 also includes a second transistor M2 that has a gate connected to the word line WORD, a drain connected to an inverted bit line /BIT, and a source connected to a second intermediate node N2.
Further, cell 100 includes a third transistor M3 that has a gate connected to the first intermediate node N1, a drain connected to the second intermediate node N2, and a source connected to ground. A fourth transistor M4, in turn, has a gate connected to the second intermediate node N2, a drain connected to the first intermediate node N1, and a source connected to ground.
In addition, cell 100 includes a fifth transistor M5 and a sixth transistor M6. Fifth transistor M5 has a gate connected to the first intermediate node N1, a drain connected to the second intermediate node N2, and a source connected to a supply voltage VCC. Sixth transistor M6 has a gate connected to the second intermediate node N2, a drain connected to the first intermediate node N1, and a source connected to the supply voltage VCC.
In operation, to program cell 100 to store, for example, a logic zero, a first positive voltage is placed on the word line WORD, ground is placed on the bit line BIT, and a second positive voltage is placed on the inverted bit line /BIT. The first and second positive voltages can be equal to, for example, the supply voltage VCC.
Under these conditions, transistor M1 pulls the voltage on the first intermediate node N1 down to ground which, in turn, turns off transistor M3 and turns on transistor M5. When transistor M5 turns on, transistor M5 pulls the voltage on the second intermediate node N2 up to the supply voltage VCC.
The rising voltage on the second intermediate node N2 turns on transistor M4 and turns off transistor M6. When transistor M4 turns on, transistor M4 additionally pulls the voltage on the first intermediate node N1 down to ground. After a programming period, the first and second positive voltages are removed. As a result of these steps, a logic zero is stored on the first intermediate node N1, and the inverse is stored on the second intermediate node N2.
To read cell 100, the first positive voltage is again placed on the word line WORD, and ground is placed on the bit line BIT. The current flow from cell 100 is then sensed to determine the state of cell 100. For example, if a logic zero is stored on the first intermediate node N1, then no current flows when ground is placed on the bit line BIT. When no current flows, the cell is read as storing a logic zero. On the other hand, if a logic one is stored on the first intermediate node N1, then a current flows when ground is placed on the bit line BIT. When current flows, the cell is read as storing a logic one.
FIG. 2 shows a circuit diagram that illustrates a prior-art, SRAM-based CAM cell 200. Cell 200 is similar to cell 100 and, as a result, utilizes the same reference numerals to designate the structures which are common to both cells. As shown in FIG. 2, cell 200 differs from cell 100 in that cell 200 has four additional transistors, which include seventh, eighth, ninth, and tenth transistors M7, M8, M9, and M10, along with a match line MATCH.
Seventh transistor M7 has a gate connected to the bit line BIT, a drain connected to the match line MATCH, and a source connected to a node N3. Eighth transistor M8 has a gate connected to the inverted bit line /BIT, a drain connected to the match line MATCH, and a source connected to a node N4.
Ninth transistor M9 has a gate connected to the first intermediate node N1, a drain connected to ground, and a source connected to node N3 and the source of transistor M7. Tenth transistor M10 has a gate connected to the second intermediate node N2, a drain connected to ground, and a source connected to node N4 and the source of transistor M8.
In operation, CAM cell 200 is programmed and read in the same manner that cell 100 is programmed and read. In addition, CAM cell 200 also supports a hardware search that determines whether a data value stored by CAM cell 200 matches a search value, known as a comparand. To conduct a search, the match line MATCH is initially pulled high via a large resistor R that is connected to the supply voltage VCC.
To determine whether the data value stored by CAM cell 200 matches a search value, the search value is placed on the bit line BIT and the inverse of the search value is placed on the inverted bit line /BIT. If the match line MATCH remains high, then a match has been detected. On the other hand, if the match line MATCH is pulled low, then no match was detected.
For example, if a logic zero is stored on the first intermediate node N1, a logic one is stored on the second intermediate node N2, a logic zero search value is placed on the bit line BIT, and a logic one is placed on the inverted bit line /BIT, the logic zero on the bit line BIT turns off transistor M7 which, in turn, prevents transistor M7 from pulling down the voltage on the match line MATCH.
In addition, although the logic one on the inverted bit line /BIT turns on transistor M8, transistor M10 remains turned off due to the logic one placed on the gate of transistor M10. As a result, the voltage on the match line MATCH remains high. Thus, since the match line MATCH was not pulled down by either transistors M7/M9 or M8/M10, the logic zero of the search value matches the logic zero stored on the first intermediate node N1.
On the other hand, if the search value is a logic one such that a logic one is placed on the bit line BIT and a logic zero is placed on the inverted bit line /BIT, then the logic one on the bit line BIT turns on transistor M7. In addition, since a logic zero is stored on the first intermediate node N1 in this example, transistor M9 is also turned on. As a result, the voltage on the match line MATCH is pulled low, thereby indicating that no match was detected.
FIG. 3 shows a circuit diagram that illustrates a prior-art, CAM cell array 300. As shown in FIG. 3, CAM cell array 300 includes a large number of CAM cells 200 that are arranged in rows and columns, where the rows represent a series of words WORD0-WORDN and the columns represent a series of bits Bit0-Bitm.
Further, CAM cell array 300 includes a series of word lines WL0-WLn such that each word line WL contacts the gates of transistors M1 and M2 of each cell 200 in a row of cells. Array 300 also includes a corresponding series of match lines ML0-MLn such that each match line ML contacts the drains of transistors M7 and M8 of each cell 200 in a row of cells.
CAM cell array 300 additionally includes a series of bit lines BL0-BLm such that each bit line BL contacts the drain of transistor M1 and the gate of transistor M7 of each cell 200 in a column of cells. Array 300 further includes a corresponding series of inverted bit lines /BL0-/BLm such that each inverted bit line /BL contacts the drain of transistor M2 and the gate of transistor M10 of each cell 200 in a column of cells.
In operation, a multi-bit binary search value is placed on the bit lines BL. For example, if the value to be searched for is 01 . . . 0, then zero is placed on bit line BL0, a one is placed on bit line BL1, and a zero is placed on bit line BLm. In addition, a one is placed on inverted bit line /BL0, a zero is placed on bit line /BL1, and a one is placed on bit line /BLm.
Under these conditions, the voltage on each match line ML0-MLn is pulled to zero unless the data value stored in a row of CAM cell array 300 exactly matches the search value. In the case where the data value stored in a row of array 300 exactly matches the search value, the voltage on the match line ML remains high.
Thus, after a search period, if a match line ML of the match lines ML0-MLn remains high, a match was found in the array. In addition, the match line ML that remains high, and the bit lines that received the search value, uniquely identify a location in CAM cell array 300 where the match resides.
As a result, when a match line ML remains high following a search to indicate that a match has been found, the address of the match line ML along with any bit line information is output as an index, and a hit signal is generated by logically ORing together all of the match lines ML0-MLn to indicate that a match has been found. Thus, a hit signal is generated each time any of the match lines ML0-MLn remain high following a search period.
When multiple hits are present, such as when some of the bits have been masked off so that the search value does not include all of the bits in a row, the lowest address and bit line information to have a hit is first output as the index. Following this, the address and bit line information of each sequential hit is sequentially clocked out as the index with a clock signal.
Although CAM cell array 300 allows the contents of the array 300 to be searched very quickly, one drawback of CAM cell array 300 is that CAM cell array 300 consumes a significant amount of power when performing a search. During a search, in each cell 200 that does not match a search value, transistors M7/M9 or transistors M8/M10 sink current from a match line ML to pull the voltage on the match line ML to ground.
As a result, in large CAM cell arrays, a large number of CAM cells 200 instantaneously and simultaneously turn on and sink current from most, if not all, of the match lines ML0-MLn to pull the voltage on the match lines ML0-MLn down to ground. As a result, large CAM cell arrays have a significant instantaneous power requirement.